#include <vector>
#include<set>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        set<vector<int>> ans;
        solve(nums, ans, 0, nums.size());
        vector<vector<int>> res;
        int size = ans.size();
        for (set<vector<int>>::iterator i = ans.begin(); i != ans.end(); i++)
        {
            res.push_back(*i);
        }
        
        return res;
    }
    void solve(vector<int> &nums, set<vector<int>> &ans, int level, int deep)
    {
        if (level == deep - 1)
        {
            ans.insert(nums);
            return;
        }
        for (int i = level; i < deep; i++)
        {
            if (i != level && nums[i] == nums[level])
            {
                continue;
            }
            swap(nums[i], nums[level]);
            solve(nums, ans, level + 1, deep);
            swap(nums[i], nums[level]);
        }
    }
};
// class Solution {
//     vector<int> vis;

// public:
//     void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
//         if (idx == nums.size()) {
//             ans.emplace_back(perm);
//             return;
//         }
//         for (int i = 0; i < (int)nums.size(); ++i) {
//             if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
//                 continue;
//             }
//             perm.emplace_back(nums[i]);
//             vis[i] = 1;
//             backtrack(nums, ans, idx + 1, perm);
//             vis[i] = 0;
//             perm.pop_back();
//         }
//     }

//     vector<vector<int>> permuteUnique(vector<int>& nums) {
//         vector<vector<int>> ans;
//         vector<int> perm;
//         vis.resize(nums.size());
//         sort(nums.begin(), nums.end());
//         backtrack(nums, ans, 0, perm);
//         return ans;
//     }
// };

int main(int argc, char const *argv[])
{
    vector<int> nums = {2,2,1, 1};
    Solution s;
    vector<vector<int>> res = s.permuteUnique(nums);

    return 0;
}
